// 2025/4/3
// https://leetcode.cn/problems/find-the-duplicate-number/description/?envType=study-plan-v2&envId=top-100-liked
// 寻找重复数

class Solution {
    public:
        int findDuplicate(vector<int>& nums) {
            int n = nums.size();
            int left = 0, right = n - 1, ans = -1;
            while(left <= right)
            {
                int mid = (left + right) >> 1;
                int count = 0;
                for(int i = 0; i < n; i++)
                {
                    count += (nums[i] <= mid);
                }
                if(count <= mid) // mid比答案小
                    left = mid + 1;
                else // mid比答案大
                {
                    right = mid - 1;
                    ans = mid;
                }
            }
            return ans;
        }
    };